package com.zhu.solution.arrayQuestion;


/*
* 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 

注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

* */

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/08/16:47
 * @Description:
 */
public class Solution_10 {

    public static void main(String[] args) {
        char[][] board_t =   {{'5','3','.','.','7','.','.','.','.'},
                            {'6','.','.','1','9','5','.','.','.'},
                            {'.','9','8','.','.','.','.','6','.'},
                            {'8','.','.','.','6','.','.','.','3'},
                            {'4','.','.','8','.','3','.','.','1'},
                            {'7','.','.','.','2','.','.','.','6'},
                            {'.','6','.','.','.','.','2','8','.'},
                            {'.','.','.','4','1','9','.','.','5'},
                            {'.','.','.','.','8','.','.','7','9'}};

        char[][] board_f =  {{'.','.','4','.','.','.','6','3','.'},
                           {'.','.','.','.','.','.','.','.','.'},
                           {'5','.','.','.','.','.','.','9','.'},
                           {'.','.','.','5','6','.','.','.','.'},
                           {'4','.','3','.','.','.','.','.','1'},
                           {'.','.','.','7','.','.','.','.','.'},
                           {'.','.','.','5','.','.','.','.','.'},
                           {'.','.','.','.','.','.','.','.','.'},
                           {'.','.','.','.','.','.','.','.','.'}};

//        boolean b = new Solution_10().isValidSudoku_2(board_f);
        boolean b = new Solution_10().isValidSudoku_3(board_f);

        System.out.println("是否是有效的数独 ： " + b);

    }

    /*有思路之后的算法，重写*/
    public boolean isValidSudoku_3(char board[][]) {

        int length = board.length;
        //定义三个二维数组，分别接受 行 列 和九宫格，相当于将列转行，9宫格一维展开。注意：int数组元素的初始值为0
        int[][] boardRow = new int[length][length];
        int[][] boardColumn = new int[length][length];
        int[][] boardNine = new int[length][length];

        //接收格子的行数字和列数字
        int num = 0;
        //k为数字所在的9宫格的顺序数
        int k = 0;

        //两个循环遍历9*9数独
        for (int i=0;i<length;i++){
            for (int j=0;j<length;j++){
                //没有数字时直接跳过
                if ('.' == board[i][j]){
                    continue;
                }
                //有数字时，将字符转为数字，用num接收数字,最后的 -1 是为了之后更好进行数组元素的非0判断
                num = board[i][j] - '0' -1 ;
                //通过i j 得到k
                k = (i/3)*3 + j/3;

                //判断是否有重复元素
                if (boardRow[i][num] !=0 || boardColumn[j][num] !=0 || boardNine[k][num] !=0){
                    return false;
                }

                //赋值不为0
                boardRow[i][num] = boardColumn[j][num] = boardNine[k][num] = 1;

            }
        }

        return true;
    }

    /*这是别人的算法*/
    public boolean isValidSudoku_2(char board[][]) {
        int length = board.length;
        //二维数组line表示的是对应的行中是否有对应的数字，比如line[0][3]
        //表示的是第0行（实际上是第1行，因为数组的下标是从0开始的）是否有数字3
        int line[][] = new int[length][length];
        int column[][] = new int[length][length];
        int cell[][] = new int[length][length];
        for (int i = 0; i < length; ++i)
            for (int j = 0; j < length; ++j) {
                //如果还没有填数字，直接跳过
                if (board[i][j] == '.')
                    continue;
                //num是当前格子的数字
                int num = board[i][j] - '0' - 1;
                //k是第几个单元格，9宫格数独横着和竖着都是3个单元格
                int k = i / 3 * 3 + j / 3;
                //如果当前数字对应的行和列以及单元格，只要一个由数字，说明冲突了，直接返回false。
                //举个例子，如果line[i][num]不等于0，说明第i（i从0开始）行有num这个数字。
                if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0)
                    return false;
                //表示第i行有num这个数字，第j列有num这个数字，对应的单元格内也有num这个数字
                line[i][num] = column[j][num] = cell[k][num] = 1;
            }
        return true;
    }


    /*以下是我的算法，蓝瘦香菇*/
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0){
            return false;
        }

        //查看数独每 行 是否有重复数字
        if (!checkRow(board,9))
            return false;

        //查看数独每 列 是否有重复数字
        if (!checkColumn(board,9))
            return false;

        //查看所有3*3数组是否有重复数字
        for (int i = 0,column=0,row=0 ; i<9;i++){
            //行列遍历
            if (i%3!=0 ){
                column+=3;
            }
            if (i!=0&&i%3==0){
                row+=3;
                column=0;
            }

            if (!check33(board,row,column))
                return false;
        }

        return true;

    }

    /**
    * @Description: 查看数组count*count数组每 行 是否有重复数字
    * @Param: [boardRow,count]
    * @return: boolean
    * @Author: zhujiabao
    * @Date: 2021/12/8
    */
    public boolean checkRow(char[][] boardRow,int count){
        for (int row = 0;row <count;row++){
            Set<Character> set = new HashSet<>();
            for (int i = 0;i<count;i++){
                if ('.' != boardRow[row][i]){
                    //如果元素重复那么返回
                    if (set.contains(boardRow[row][i]))
                        return false;
                    //没有重复继续加入
                    set.add(boardRow[row][i]);
                }
            }
        }
        return true;
    }

    /**
    * @Description: 查看数组count*count数组每 列 是否有重复数字
    * @Param: [boardRow, count]
    * @return: boolean
    * @Author: zhujiabao
    * @Date: 2021/12/8
    */
    public boolean checkColumn(char[][] boardRow,int count){
        for (int column = 0;column <count;column++){
            Set<Character> set = new HashSet<>();
            for (int i = 0;i<9;i++){
                if ('.' != boardRow[i][column]){
                    //如果元素重复那么返回
                    if (set.contains(boardRow[i][column]))
                        return false;
                    //没有重复继续加入
                    set.add(boardRow[i][column]);
                }
            }
        }
        return true;
    }

    //查看某个3*3数组是否有重复数字
    public boolean check33(char[][] boardRow,int row,int column){
        Set<Character> set = new HashSet<>();
        int rowTemp=row;
        int columnTemp=column;
        for (int i = 0;i<9;i++){
            //行列遍历
            if (i%3!=0 ){
                columnTemp++;
            }
            if (i!=0&&i%3==0){
                rowTemp++;
                columnTemp=column;
            }
            //检查重复
            if ('.' != boardRow[rowTemp][columnTemp]){
                //如果元素重复那么返回
                if (set.contains(boardRow[rowTemp][columnTemp]))
                    return false;
                //没有重复继续加入
                set.add(boardRow[rowTemp][columnTemp]);
            }


        }

        return true;
    }
}
